#include "calculator.h"

Calculator::Calculator()
{

}

//字符串转中缀表达式
void Calculator::stringToInfixExpression(QString str){
    QString tempString = "";
    infixExpression = new QVector<QString>();
    for (int i = 0; i < str.length(); i++) {
        if (str.at(i).isDigit() || str.at(i).toAscii() == '.') {
            tempString += str.at(i);
        }
        if (str.at(i).toAscii() == '+' || str.at(i).toAscii() == '-' || str.at(i).toAscii() == '*' || str.at(i).toAscii() == '/' || str.at(i).toAscii() == '(' || str.at(i).toAscii() == ')') {
            if (!tempString.isEmpty())
                infixExpression->append(tempString);
            tempString = "";
            infixExpression->append(str.mid(i, 1));
        }
    }
    infixExpression->append(QString(tempString));
}

//中缀表达式转后缀表达式
void Calculator::infixExpressionToPostfixExpression(){
    postfixExpression = new QVector<QString>();
        QStack<QString> stack;
//            qDebug()<<"===infixExpressionToPostfixExpression====";
//            for (int i = 0; i < this->infixExpression->size(); ++i) {
//                 qDebug()<<this->infixExpression->at(i);
//             }

//            for (QString str : infixExpression) {
        for (int i = 0; i < this->infixExpression->size(); ++i) {
    /*
    //如果扫描到的字符是一个操作符，分三种情况：
    //（1）如果堆栈是空的，直接将操作符存储到堆栈中（push it）
    //（2）如果该操作符的优先级大于堆栈出口的操作符，就直接将操作符存储到堆栈中（push it）
    //（3）如果该操作符的优先级低于堆栈出口的操作符，就将堆栈出口的操作符导出（pop it）,
           直到该操作符的优先级大于堆栈顶端的操作符。将扫描到的操作符导入到堆栈中（push）。
    // 如果遇到的操作符是左括号"（”，就直接将该操作符输出到堆栈当中。该操作符只有在遇到右括号“)”
    的时候移除。这是一个特殊符号该特殊处理。
    //如果扫描到的操作符是右括号“）”，将堆栈中的操作符导出（pop）到output中输出，直到遇见左括号“（”。
    将堆栈中的左括号移出堆栈（pop ）。继续扫描下一个字符
    //如果输入的中缀表达式已经扫描完了，但是堆栈中仍然存在操作符的时候，我们应该讲堆栈中的操作符导出并输入到output 当中。
    */
        QString str = infixExpression->at(i);
        if (str.compare("+")==0 || str.compare("-")==0 || str.compare("*")==0 || str.compare("/")==0) {
//              qDebug()<<str;
            if (stack.isEmpty()) {
                stack.push(str);
            } else if (getPriority(str) > getPriority(stack.top())) {
                stack.push(str);
            } else {
                while (true) {
                    if (stack.isEmpty()) {
                        stack.push(str);
                        break;
                    } else if (getPriority(str) > getPriority(stack.top())) {
                        stack.push(str);
                        break;
                    }
                    postfixExpression->append(stack.pop());
                }
            }
        }
        else if (str.compare("(") == 0) {
            stack.push(str);
        } else if (str.compare(")") == 0) {
            while (true) {
                if (stack.top().compare("(") == 0) {
                    stack.pop();
                    break;
                }
                postfixExpression->append(stack.pop());
            }
        } else {
            postfixExpression->append(str);
        }
    }
    while (!stack.isEmpty()) {
        postfixExpression->append(stack.pop());
    }
//            return postfixExpression;
}
//后缀表达式求值
double Calculator::evaluatePostfixExpressions(){
/*
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，
弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），
并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
*/
    QStack<double> doubleStack;
    double num1 = 0.0, num2 = 0.0, tempResult = 0.0;
//    for (QString string : postfixExpressions) {
    for (int i = 0; i < this->postfixExpression->size(); ++i) {
        QString string = postfixExpression->at(i);
        if (string.compare("+")==0 || string.compare("-")==0 || string.compare("*")==0 || string.compare("/")==0) {
            num1 = doubleStack.pop();
            num2 = doubleStack.pop();
            switch (string[0].toAscii()) {
                case '+':
                    tempResult = num2 + num1;
                    break;
                case '-':
                    tempResult = num2 - num1;
                    break;
                case '*':
                    tempResult = num2 * num1;
                    break;
                case '/':
                    tempResult = num2 / num1;
                    break;
                default:
                    break;
            }
            doubleStack.push(tempResult);
        } else {
            doubleStack.push(string.toDouble());
        }
    }
    return doubleStack.top();
}

//获取优先级
int Calculator::getPriority(QString op){
    int priority = 0;
    switch (op[0].toAscii()) {
        case '+':
        case '-':
            priority = 1;
            break;
        case '*':
        case '/':
            priority = 2;
            break;
        default:
            break;
    }
    return priority;
}

//计算最终结果
double Calculator::calculator(QString s){
    this->stringToInfixExpression(s);
    for (int i = 0; i < this->infixExpression->size(); ++i) {
         qDebug()<<this->infixExpression->at(i);
     }
    this->infixExpressionToPostfixExpression();
    qDebug()<<"val="<<this->evaluatePostfixExpressions();
    return this->evaluatePostfixExpressions();
}
